package com.le.medium.class6;

import org.junit.Test;

/**
 * 给定一个整型矩阵，返回子矩阵的最大累计和。
 * 思路：
 * 0-0最大值
 * 0-1行最大值
 * 0-2行最大值
 * 。。。。
 * 0-0-1-2： 多行求最大值采用压缩矩阵求
 */
public class Problem07_SubMatrixMaxSum {

    public static int maxSum(int[][] m) {
        if (m == null || m.length == 0 || m[0].length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        int[] s = null;
        for (int i = 0; i < m.length; i++) {
            s = new int[m[0].length];
            for (int j = i; j != m.length; j++) {
                cur = 0;
                // 子数组求最大累加和
                for (int k = 0; k < s.length; k++) {
                    s[k] += m[j][k];
                    cur += s[k];
                    max = Math.max(cur, max);
                    cur = cur < 0 ? 0 : cur;
                }
            }
        }
        return max;
    }

    @Test
    public void test(){
        int[][] matrix = {
                { -90, 48, 78 },
                { 64, -40, 64 },
                { -81, -7, 66 }
        };
        System.out.println(maxSum(matrix));
    }
}
